\subsubsection{Übung (viii)}

\paragraph{Aufgabe:}
In dieser Aufgabe seien die beim Secret-Sharing beteiligten Parteien mit $P_1, P_2, \ldots$ bezeichnet. Aufgrund ihrer Rollen im System können die einzelnen Parteien auch mehr als einen Geheimnisanteil (share) erhalten, etwa in einer Konstellation, in der fünf Mitarbeiter gemeinsam das Geheimnis wiederherstellen können, aber  bereits drei Abteilungsleiter ausreichen, um dasselbe zu tun.

\begin{itemize}
\item
Konzipieren Sie ein Secret-Sharing-System für sechs Personen, so dass nur genau die folgenden Teilmengen der Menge $P := \{ P_1, \ldots, P_6 \}$ das Geheimnis wiederherstellen können: 
\[ 
  \{ P_1, P_2 \}, \: \: \{ Q \subseteq P : |Q| \ge 3 \wedge P_1 \in Q \}, \: \: \{ Q \subseteq P : |Q| \ge 4 \wedge P_2 \in Q \}
\]

\item
Ist es möglich, mit Hilfe von Secret-Sharing-Verfahren in einer Menge $P = \{ P_1, \ldots, P_4 \}$ ein Geheimnis derart zu teilen, dass nur genau die Gruppen $Q \subseteq P$ zur Wiederherstellung befähigt sind, für die $\{ P_1, P_2 \} \subseteq Q$ oder $\{ P_3, P_4 \} \subseteq Q$ gilt?
\end{itemize}

\paragraph{Lösung: Secret-Sharing für sechs Personen:}
Eine Lösungsansatz besteht in der Konzeption eines (9,5)-Secret-Sharing. Es werden $n=9$ Geheimnisanteile berechnet von deren $t=5$ zur Rekonstruktion benötigt werden. Die Anzahl der Geheimnisanteile erklärt sich wie folgt:

\begin{itemize}
\item $P_1, P_2$ können das Geheimnis gemeinsam rekonstruieren.
\item $P_1$ und mindestens zwei Weitere können das Geheimnis rekonstruieren.
\item $P_2$ und mindestens drei Weitere können das Geheimnis rekonstruieren.
\end{itemize}

Damit müssen $P_1$ und $P_2$ die Hälfte der Geheimnisanteile besitzen. Da $P1$ nur zwei Weitere benötigt, um das Geheimnis zu rekonstruieren und $P2$ derer drei besitzt $P1$ mehr Geheimisanteile als $P2$. Eine mögliche Verteilung der Geheimnisanteile ist daher:

\begin{itemize}
\item $P_1$: ($x_{1},y_{1}$),($x_{2},y_{2}$),($x_{3},y_{3}$)
\item $P_2$: ($x_{4},y_{4}$),($x_{5},y_{5}$)
\item $P_3$: ($x_{6},y_{6}$)
\item $P_4$: ($x_{7},y_{7}$)
\item $P_5$: ($x_{8},y_{8}$)
\item $P_6$: ($x_{9},y_{9}$)
\end{itemize}

Für die Berechnung der Geheimnisanteile gilt:
\begin{itemize}
\item $p = 37$
\item $s = 7$
\item $x_{i} = i$, $1 \leq i \leq 9$
\item $a(X) = 7 + 2X +3X^2 +4X^3 +5X^4$
\end{itemize}

\subparagraph{Berechnung der Geheimnisanteile:}
\begin{itemize}
\item $a(1) = 7 + 2 + 3 + 4 + 5 \mod 37 = 21$
\item $a(2) = 7 + 4 + 12 + 32 + 80 \mod 37 = 24$
\item $a(3) = 7 + 6 + 27 + 108 + 405 \mod 37 = 35$
\item $a(4) = 7 + 8 + 48 + 256 + 1280 \mod 37 = 8$
\item $a(5) = 7 + 10 + 75 + 500 + 3125 \mod 37 = 17$
\item $a(6) = 7 + 12 + 108 + 864 + 6480 \mod 37 = 34$
\item $a(7) = 7 + 14 + 147 + 1372 + 12005 \mod 37 = 3$
\item $a(8) = 7 + 16 + 192 + 2048 + 20480 \mod 37 = 25$
\item $a(9) = 7 + 18 + 243 + 2916 + 32805 \mod 37 = 25$
\end{itemize}

\subparagraph{Rekonstruktion ${P1, P2}$:}
\[
L_1 = \frac{2 * 3 * 4 * 5}{(2-1)*(3-1)*(4-1)*(5-1)}=\frac{120}{24} = 5
\]
\[
L_2 = \frac{1 * 3 * 4 * 5}{(1-2)*(3-2)*(4-2)*(5-2)}=-\frac{60}{6} = -10
\]
\[
L_3 = \frac{1 * 2 * 4 * 5}{(1-3)*(2-3)*(4-3)*(5-3)}=\frac{40}{4} = 10
\]
\[
L_4 = \frac{1 * 2 * 3 * 5}{(1-4)*(2-4)*(3-4)*(5-4)}=-\frac{30}{6} = -5
\]
\[
L_5 = \frac{1 * 2 * 3 * 4}{(1-5)*(2-5)*(3-5)*(4-5)}=\frac{24}{24} = 1
\]

\[
a(0) = L_1 * y_{1} - L_2 * y_{2} + L_3 * y_{3} - L_4 * y_{4} + L_5 * y_{5}
\]
\[
a(0) = (5 * 21 - 10 * 24 + 10 * 35 -5 * 8 + 1 * 17) \mod 37
\]
\[
a(0) = 185 \equiv 7 \mod37
\]

\paragraph{Lösung: Secret-Sharing in einer Menge $P := \{ P_1, \ldots, P_6 \}$:} Ein Lösungsansatz besteht in der Konzeption zweier $(2,2)$-Secret-Sharing-Verfahren. Damit gelten $n=2$ und $t=2$. Zusätzlich seien $s = 3$ und $p = 11$.

\subparagraph{1. $(2,2)$-Secret-Sharing-Verfahren:} Mit $t=2$ und $s=3$ wird ein Polynom $a(X)$ bestimmt.
\[
a(X)= 3 + 2X
\]

Durch Einsetzen der Stützwerte $x_1=1$ und $x_2=2$ können die Stützstellen $y_1$ und $y_2$ berechnet werden: 

\begin{itemize}
\item $a(1) = 3 + 2 * 1 = 5 \mod 11 = 5$
\item $a(2) = 3 + 2 * 2 = 7 \mod 11 = 7$
\end{itemize}

Damit exisitieren die folgenden beiden Paare, die an $P_1$ und $P_2$ verteilt werden.

\begin{itemize}
\item ($1,7$)
\item ($2,9$)
\end{itemize}

\subparagraph{2. $(2,2)$-Secret-Sharing-Verfahren:} Mit $t=2$ und $s=3$ wird ein anderes Polynom $b(X)$ bestimmt.
\[
b(X)= 3 + 5X
\]

Auch hier werden durch Einsetzen der Stützwerte $x_1=1$ und $x_2=2$ die Stützstellen $y_1$ und $y_2$ berechnet: 

\begin{itemize}
\item $b(1) = 3 + 5 * 1 = 8 \mod 11 = 8$
\item $b(2) = 3 + 5 * 2 = 13 \mod 11 = 2$
\end{itemize}

Damit exisitieren die folgenden beiden Paare, die an $P_3$ und $P_4$ verteilt werden.

\begin{itemize}
\item ($1,8$)
\item ($2,2$)
\end{itemize}

\subparagraph{Rekonstruktion durch $\{P1, P2\}$:}
\[
L_1(0) = \frac{2}{2-1} = 2
\]

\[
L_2(0) = \frac{1}{1-2} = -1
\]

\[
a(0) = L_1(0) * y_1 - L_2(0) * y_2 = 2 * 5 + (-1) * 7 = 3 \mod 11 = 3
\]

Das Geheimnis lässt sich also aus $\{P1, P2\}$ rekonstruieren.

\subparagraph{Rekonstruktion durch $\{P3, P4\}$:}
\[
L_1(0) = \frac{2}{2-1} = 2
\]

\[
L_2(0) = \frac{1}{1-2} = -1
\]

\[
a(0) = L_1(0) * y_1 - L_2(0) * y_2 = 2 * 8 + (-1) * 2 = 14 \mod 11 = 3
\]

Das Geheimnis lässt sich also aus $\{P3, P4\}$ rekonstruieren.

\subparagraph{Keine Rekonstruktion durch $\{P1, P4\}$:}
\[
L_1(0) = \frac{2}{2-1} = 2
\]

\[
L_2(0) = \frac{1}{1-2} = -1
\]

\[
a(0) = L_1(0) * y_1 - L_2(0) * y_2 = 2 * 5 + (-1) * 2 = 7 \mod 11 = 7 \neq 3
\]

Das Geheimnis lässt sich also aus $\{P1, P4\}$  \textbf{nicht rekonstruieren}.

\subparagraph{Keine Rekonstruktion durch $\{P2, P3\}$:}
\[
L_1(0) = \frac{2}{2-1} = 2
\]

\[
L_2(0) = \frac{1}{1-2} = -1
\]

\[
a(0) = L_2(0) * y_2 - L_1(0) * y_1 = 2 * 7 + (-1) * 8 = 6 \mod 11 = 6 \neq 3
\]

Das Geheimnis lässt sich also aus $\{P2, P3\}$  \textbf{nicht rekonstruieren}.
